package src.com.test.oneDay;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class demo2 {


    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum3(int k, int n) {

        tracebacking(k,n,1);
        return res;

    }
    public void tracebacking(int k,int n,int startIndex){

        if(path.size() == 3 && sum == n){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex;i <= 9;i++){
            path.add(i);
            sum += i;
            tracebacking(k,n,i+1);
            path.removeLast();
            sum -= i;
        }
    }

    public void tracebacking2(int k,int n,int startIndex){

        if(path.size() == 3 && sum == n){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex;i < 9 - (k - path.size()) + 1;i++){
            path.add(i);
            sum += i;
            if(sum > k){
                path.removeLast();
                sum -= i;
                return;
            }
            tracebacking2(k,n,i+1);
            path.removeLast();
            sum -= i;
        }
    }


}
